package algorithm.leetcode.I401to600;


/**
 * 看成一个0-1背包问题,即nums中的数字是否可以构成总和的一半
 * 一些早停(直接返回false)的条件: 总和为奇数,最大值大于总和的一半
 *
 * dp[i,j] = f(dp[i-1,j], dp[i-1,j-options[i]])
 * 翻译成人话就是,第i个选择出来之后,状态j与 前i-1个选择的状态j(不用第i个选择) 以及 前i-1个选择的状态j-option[i](用第i个选择) 有关
 * 当然上面的数组索引不能越界
 */

// e.g. [1,5,11,5], sum=22,一半即为11
//    0  1  2  3  4  5  6  7  8  9  10  11
// 0  T  F  F  F  F  F  F  F  F  F   F   F
// 1  T  T  F  F  F  F  F  F  F  F   F   F
// 5  T  T  F  F  F  T  T  F  F  F   F   F
// 11 T  T  F  F  F  T  T  F  F  F   F   T
// 5  T  T  F  F  F  T  T  F  F  F   T   T

public class Q416 {

    public boolean canPartition(int[] nums) {
        int target = 0, max = Integer.MIN_VALUE;
        for (int num : nums) {
            target += num;
            max = Math.max(num, max);
        }
        if ((target&1) == 1) return false;
        target >>= 1;
        if (max > target) return false;

        // 题目保证了和是正的
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for (int num : nums) {
            boolean[] backup = dp;
            dp = new boolean[target+1];
            for (int i = 0; i <= target; i++) {
                if (i - num < 0) dp[i] = backup[i];
                else dp[i] = backup[i] || backup[i-num];
            }
        }
        return dp[target];
    }

}
